import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


class Solution {
    public static int minNumberOfFrogs(String croakOfFrogs) {
        char[] str = croakOfFrogs.toCharArray();
        String tmp = "croak";
        int len = tmp.length();
        int[] hash = new int[len];

        Map<Character, Integer> index = new HashMap<>();
        for(int i = 0; i < len; i++){
            index.put(tmp.charAt(i), i);
        }
        for(char ch : str){
            if(ch == tmp.charAt(0)){
                if(hash[len - 1] != 0){
                    hash[len - 1]--;
                }else{
                    hash[0]++;
                }
            }else{
                int k = index.get(ch);
                if(hash[k - 1] == 0){
                    return -1;
                }else{
                    hash[k - 1]--;
                    hash[k]++;
                }
            }
        }

        for(int i = 0; i < len - 1; i++){
            if(hash[i] != 0){
                return -1;
            }
        }
        return hash[len - 1];
    }


    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode head = new ListNode(-1);
        ListNode last = head;
        int t = 0;

        while(cur1 != null || cur2 != null || t != 0){
            if(cur1 != null){
                t += cur1.val;
                cur1 = cur1.next;
            }
            if(cur2 != null){
                t += cur2.val;
                cur2 = cur2.next;
            }
            last.next = new ListNode(t % 10);
            last = last.next;
            t /= 10;
        }
        return head.next;
    }


    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) { return head;}
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode prev = newHead, cur = head, next = head.next, nnext = next.next;

        while(cur != null && next != null){
            prev.next = next;
            next.next = cur;
            cur.next = nnext;

            prev = cur;
            cur = nnext;
            if(cur != null) { next = cur.next;}
            if(next != null) { nnext = next.next;}
        }
        return newHead.next;
    }


    public void reorderList(ListNode head) {
        if(head == null || head.next == null) { return ;}

        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode head2 = new ListNode(-1);
        ListNode cur = slow.next;
        slow.next = null;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = tmp;
        }

        ListNode cur1 = head, cur2 = head2.next;
        ListNode ret = new ListNode(-1);
        ListNode prev = ret;
        while(cur1 != null){
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;

            if(cur2 != null){
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }


    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int i, int j){
        if(i > j) { return null;}
        if(i == j) { return lists[i];}

        int mid = (i + j) / 2;
        ListNode l1 = merge(lists, i, mid);
        ListNode l2 = merge(lists, mid + 1, j);
        return mergeTwo(l1, l2);
    }
    public ListNode mergeTwo(ListNode l1, ListNode l2){
        if(l1 == null) { return l2;}
        if(l2 == null) { return l1;}

        ListNode ret = new ListNode(-1);
        ListNode cur1 = l1, cur2 = l2, tmp = ret;

        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                tmp.next = cur1;
                tmp = cur1;
                cur1 = cur1.next;
            }else{
                tmp.next = cur2;
                tmp = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 != null) { tmp.next = cur1;}
        if(cur2 != null) { tmp.next = cur2;}
        return ret.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        //1.创建一个小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2) -> v1.val - v2.val);
        //2.把所有的头结点放进小根堆
        for(ListNode head : lists){
            if(head != null){
                heap.offer(head);
            }
        }
        //3.合并链表
        ListNode ret = new ListNode(-1);
        ListNode prev = ret;
        while(!heap.isEmpty()){
            ListNode t = heap.poll();
            prev.next = t;
            prev = prev.next;
            if(t.next != null){ heap.offer(t.next);}
        }
        return ret.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            cur = cur.next;
            count++;
        }
        count /= k;

        ListNode newHead = new ListNode(-1);
        ListNode prev = newHead;
        cur = head;
        for(int i = 0; i < count; i++){
            ListNode tmp = cur;
            for(int j = 0; j < k; j++){
                ListNode next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev.next = cur;
        return newHead.next;
    }


















































    public static void main(String[] args) {
        String str =  "croakcroak";
        System.out.println(minNumberOfFrogs(str));
    }
}